1. Field of the Invention
The invention relates to an apparatus for scheduling packets and a method of doing the same, and more particularly to such an apparatus and a method which accumulates packets in packet cues in dependence on a class.
2. Description of the Related Art
In a field of exchanging packets, quality of service (QOA) guaranteed by a network is grouped into a plurality of ranks or kinds called classes. A network for exchanging packets assigns a wide bandwidth to a packet belonging o a class having high priority, and assigns a narrow bandwidth to a packet belonging to a class having low priority, to thereby guarantee quality of service for each of classes.
A packet exchanger in a network for exchanging packets usually includes an apparatus for scheduling packets for determining an order in which received packets are transmitted, in order to guarantee quality of service which is different from others in classes. FIG. 1 is a block diagram of a conventional apparatus for scheduling packets.
The apparatus for scheduling packets, illustrated in FIG. 1, carries out weighted round robin (WRR) scheduling. The weighted round robin scheduling is characterized in that it is not necessary to sort received packets, it is possible to assign a maximum transmission bandwidth to each of classes, and there is no problem that packets belonging to the same class are continuously transmitted, in other words, the weighted round robin scheduling has superior fairness characteristic.
The apparatus for scheduling packets, illustrated in FIG. 1, is comprised of a common buffer 1, a packet-writing controller 2, a packet-reading controller 3, a cue length administrator 4, a scheduler 5, and a token administrator 6.
The common buffer 1 includes N packet cues associated with classes #1 to #N.
On receipt of a packet, the packet-writing controller 2 identifies a class to which the received packet belongs, based on data stored in a header field of the received packet. Based on the identification, the packet-writing controller 2 writes the received packet into a packet cue associated with the identified class. In addition, the packet-writing controller 2 transmits data such as a class and a length of the received packet to the cue length administrator 4 as packet-writing data.
The packet-reading controller 3 reads a header packet out of a packet cue associated with a class identified by the scheduler 5 by means of an output class number OC, and outputs the thus read-out packet. The packet-reading controller 3 transmits a length of the read-out packet PL together with the output class number OC to the token administrator 6. In addition, the packet-reading controller 3 transmits data such as a class and a length of the read-out packet to the cue length administrator 4 as packet-reading data.
The cue length administrator 4 administers a number of and lengths of packets stored in each of the packet cues, based on the packet-writing data received from the packet-writing controller 2 and the packet-reading data received from the packet-reading controller 3.
The cue length administrator 4 transmits an effective packet bit series VS to the scheduler 5. The effective packet bit series indicates whether a transmittable packet is accumulated in each of the packet cues #1 to #N. The effective packet bit is comprised of a bit series signal having N bits where each of bits corresponds to each of the packet cues one by one. That is, the effective packet bit series indicates “1” for a bit in which a transmittable packet is accumulated in the associated packet cue, and indicates “0” for a bit in which a transmittable packet is not accumulated in the associated packet cue.
The scheduler 5 determines a class to which a packet to be transmitted next belongs, based on both the effective packet bit series VS received from the cue length administrator 4 and a transmission allowance bit series SS received from the token administrator 6, and transmits the thus determined class to the packet-reading controller 3 as the above mentioned output class number OC. Herein, the transmission allowance bit series SS is comprised of a bit series signal having N bits where each of bits corresponds to each of the classes one by one. That is, a bit associated with a class where the token administrator 6 allows transmission of a packet is expressed as “1”, and a bit associated with a class where the token administrator 6 does not allow transmission of a packet is expressed as “0”.
The scheduler 5 selects one class in round robin fashion among classes where both of the effective packet bit series VS and the transmission allowance bit series indicate “1”. The output class number OC is a number of the thus selected class.
The scheduler 5 transmits a request AR of addition of a token to the token administrator 6, when predetermined conditions are satisfied. The predetermined conditions are dependent on an algorithm defining an operation of the scheduler 5. There are two typical conditions as the predetermined conditions, as follows.
One of the typical conditions is that there is no packet to be transmitted. That is, there is not a class where both of the effective packet bit series VS and the transmission allowance bit series SS indicate “1”. In a packet scheduling apparatus in which the scheduler 5 transmits a request AR of addition of a token to the token administrator 6 when there is no packet to be transmitted, it would be possible to transmit packets in accordance with a bandwidth ratio determined in each of classes. In such a packet scheduling apparatus, if input traffic is small in a certain class, the rest of bandwidth is used in accordance with a bandwidth of other classes in order to transmit packets of the other classes.
The other of the typical conditions is that a predetermined period of time has passed. In this case, the scheduler 5 periodically transmits a request of addition of a token to the token administrator 6. In a packet scheduling apparatus in which a request of addition of a token is periodically transmitted to the token administrator 6, it would be possible to set a maximum transmission rate in each of classes. This is effective to not only a class or packet cue controlled by a round robin scheduler, but also to a packet of a class for best effort.
The token administrator 6 administers a token for each of classes. Specifically, on receipt of a request of addition of a token from the scheduler 5, the token administrator 6 adds an additional token weighted with a weight in advance defined for each of classes, to a token associated with each of classes.
In addition, on receipt of an output class number and a packet length from the packet-reading controller 3, the token administrator 6 subtracts a token equivalent to the received packet length from a token of the associated class. Then, the token administrator 6 compares a token of each of classes to a predetermined token. If a token is equal to or greater than the predetermined token, the token administrator 6 transmits a transmission allowance bit series SS in which the associated bit is set equal to 1, whereas if a token is smaller than the predetermined token, the token administrator 6 transmits a transmission allowance bit series SS in which the associated bit is set equal to zero.
FIG. 2 is a block diagram of the token administrator 6.
As illustrated in FIG. 2, the token administrator 6 is comprised of first to N-th circuits 7-1 to 7-N (N is an integer equal to or greater than 2) each carrying out addition and subtraction of a token in each of classes, and a circuit 8 for updating a transmission allowance flag, electrically connected to each of the first to N-th circuits 7-1 to 7-N.
Each of the first to N-th circuits 7-1 to 7-N stores a token which is a variable, an additional token and a maximum token as parameters. The additional token and the maximum token are in advance determined for each of classes.
On receipt of a request of addition of a token from the scheduler 5, each of the first to N-th circuits 7-1 to 7-N adds the additional token to a token. If a sum of the additional token and a token were over the maximum token, each of the first to N-th circuits 7-1 to 7-N equalizes a token to the maximum token.
When each of the first to N-th circuits 7-1 to 7-N receives an output class number from the packet-reading controller 3 which number is a number of a class of which each of the first to N-th circuits 7-1 to 7-N is in charge, each of the first to N-th circuits 7-1 to 7-N subtracts a token equivalent to the packet length transmitted from the packet-reading controller 3, from a token.
After addition or subtraction of a token, if a token is equal to or greater than zero, each of the first to N-th circuits 7-1 to 7-N transmits a request to the flag updating circuit 8 to set a transmission allowance bit of the associated class equal to 1, whereas if a token is smaller than zero, each of the first to N-th circuits 7-1 to 7-N transmits a request to the flag updating circuit 8 to set a transmission allowance bit of the associated class equal to zero.
The circuit 8 for updating a transmission allowance flag has transmission allowance flags associated with the classes. The circuit 8 turns the transmission allowance flags to 1 or 0 in compliance with a request transmitted from each of the first to N-th circuits 7-1 to 7-N. The transmission allowance flags are output to the scheduler 5 from the circuit 8 as the transmission allowance bit series SS.
In such a manner as mentioned above, the conventional packet scheduling apparatus transmits packets having been grouped into each of classes, to each of classes with quality of service associated with each of classes being guaranteed.
The above-mentioned conventional apparatus for scheduling packets is necessary to include a token register for storing a token therein, and a circuit for carrying out addition or subtraction of a token, for each of classes. Accordingly, if a number of classes is to be increased, it would be unavoidable for the conventional packet scheduling apparatus to become larger in a size. Thus, the conventional packet scheduling apparatus is accompanied with a problem that a maximum number of classes is about 10 at greatest.
An apparatus for scheduling packets in weighted round robin (WRR) scheduling process is suggested, for instance, in Japanese Unexamined Patent Publications Nos. 9-83547, 10-84383, 10-200532, 2000-299686 and 2001-53807. However, the apparatuses suggested in these Publications are accompanied with a problem that an increase in a number of classes would cause an increase in a size of an apparatus, similarly to the above-mentioned conventional packet scheduling apparatus.